# 第 3 节 最常用的排序——快速排序
# 时间复杂度：最差O( N2)，平均时间复杂度为 O( Nlog N)

def quick_sort(left, right, array):
    i = left
    j = right
    if left > right:
        return
        # 基数取左边第一个
    temp = array[left]
    while i != j:
        # 顺序很重要，要先从右往左找。为什么？
        # 先从在边开始时，那么 i 所停留的那个位置肯定是大于基数6的
        while (a[j] >= temp) and (i < j):
            j = j - 1
        # 再从左往右找
        while (a[i] <= temp) and (i < j):
            i = i + 1
        # 当哨兵i和哨兵j没有相遇时 交换位置
        if i < j:
            t = array[j]
            array[j] = array[i]
            array[i] = t
    # print(i)
    # 将基数 temp放到i的位置，左边都是小于基数的，右边都是大于基数的
    array[left] = array[i]
    array[i] = temp
    # 递归
    quick_sort(left, i - 1, a)
    quick_sort(i + 1, right, a)


if __name__ == '__main__':
    a = [6, 1, 2, 7, 9, 3, 4, 5, 10, 8]
    print("数组：", a)
    quick_sort(0, len(a) - 1, a)
    print("结果：", a)
